package com.company.algo.DichotomousSearch;

/**
 * @Author ChanZany
 * @Date 2021/7/3 11:28
 * @Version 1.0
 * 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去
 */
public class Sqrt {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        int l = 1, r = x, mid, sqrt;
        while (l <= r) {                        //注意这个<=
            mid = (l + r) / 2;
            sqrt = x / mid;
            if (sqrt == mid) return mid;
            else if (sqrt > mid) l = mid + 1;   //说明mid小了
            else r = mid - 1;
        }
        return r;                               //向下取整
    }

    //牛顿法：((n+x/n)/2 >= sqrt(x))
    public int newton(int x){
        return (int)sqrt(x,x);
    }

    private double sqrt(double i, int x){
        double res = (i + x/i)/2;
        if (res == i) return i;
        else return sqrt(res,x);
    }

    public static void main(String[] args) {
        System.out.println(new Sqrt().newton(8));
    }

}
